package com.base.unionFindSets;

import java.util.*;

/**
 * 352. 将数据流变为多个不相交区间
 * <p>
 * 给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
 * <p>
 * 实现 SummaryRanges 类：
 * <p>
 * SummaryRanges() 使用一个空数据流初始化对象。
 * void addNum(int val) 向数据流中加入整数 val 。
 * int[][] getIntervals() 以不相交区间 [starti, endi] 的列表形式返回对数据流中整数的总结。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author leon
 * @date 2021年10月09日 15:21
 */
public class SummaryRanges {
    /**
     * 并查集
     */
    private int[] father = new int[10001];
    /**
     * 保存每个区间的左边界
     */
    private Set<Integer> set = new TreeSet<>();

    public SummaryRanges() {
        Arrays.fill(father, -1);
    }

    private int find(int val) {
        if (father[val] != val) {
            return father[val] = find(father[val]);
        }
        return father[val];

    }

    public void addNum(int val) {
        if (father[val] == -1) {
            father[val] = val;
            set.add(val);
            //先合并右边，在合并左边
            union(val, val + 1);
            union(val - 1, val);
        }
    }

    private void union(int start, int end) {
        if (start >= 0 && end <= father.length - 1 && father[start] != -1 && father[end] != -1) {
            int fs = find(start);
            int fe = find(end);
            if (fs != fe) {
                father[start] = fe;
                //合并集合过后，可以移除左边界
                set.remove(end);
            }
        }
    }

    public int[][] getIntervals() {
        List<int[]> list = new ArrayList<>();
        // 遍历左边界集合
        for (Integer i : set ) {
                int start = i;
                int end = find(start);
                list.add(new int[]{start, end});
        }
        return list.toArray(new int[list.size()][2]);
    }

}
